Convex hull and intersection

Introduction

These examples illustrate common operations on polyhedra using Polyhedra.jl:

The convex hull of the union of polytopes
The intersection of polytopes

We start by choosing a polyhedral library that will be used for computing the H-representation from the V-representation and vice-versa as well as removing redundant points. In these example, we use the default library available in Polyhedra but it can be replaced by any other library listed here, e.g. by changing the last two lines below by import CDDLib and lib = CDDLib.Library() to use CDDLib.

using Polyhedra
import GLPK
lib = DefaultLibrary{Float64}(GLPK.Optimizer)

DefaultLibrary{Float64}(GLPK.Optimizer)

Convex hull

The binary convex hull operation between two polyhedra is obtained with the convexhull function.

Below we compute the convex hull of the union of two polygons from their V-representation.

P1 = polyhedron(vrep([
    -1.9 -1.7
    -1.8  0.5
     1.7  0.7
     1.9 -0.3
     0.9 -1.1
]), lib)

P2 = polyhedron(vrep([
    -2.5 -1.1
    -0.8  0.8
     0.1  0.9
     1.8 -1.2
     1.3  0.1
]), lib)

Pch = convexhull(P1, P2)

Polyhedron DefaultPolyhedron{Float64, MixedMatHRep{Float64, Matrix{Float64}}, MixedMatVRep{Float64, Matrix{Float64}}}:
10-element iterator of Vector{Float64}:
 [-1.9, -1.7]
 [-1.8, 0.5]
 [1.7, 0.7]
 [1.9, -0.3]
 [0.9, -1.1]
 [-2.5, -1.1]
 [-0.8, 0.8]
 [0.1, 0.9]
 [1.8, -1.2]
 [1.3, 0.1]

Note that the convex hull operation is done in the V-representation so no representation conversion is needed for this operation since P1 and P2 where constructed from their V-representation:

hrepiscomputed(P1), hrepiscomputed(P2), hrepiscomputed(Pch)

(false, false, false)

Let us note that the convexhull of a V-representation contains points and rays and represents the convex hull of the points together with the conic hull of the rays. So, convexhull(P1, P2) does the union of the vertices:

npoints(Pch)

However, if we want to remove the redundant points we can use removevredundancy!:

removevredundancy!(Pch)
npoints(Pch)

We can plot the polygons and the convex hull of their union using the plot function. For further plotting options see the Plots.jl documentation. We can see below the 8 redundant points highlighted with green dots, the two points that are not highlighted are the redundant ones.

using Plots
plot(P1, color="blue", alpha=0.2)
plot!(P2, color="red", alpha=0.2)
plot!(Pch, color="green", alpha=0.1)
scatter!(Pch, color="green")

Intersection

Intersection of polyhedra is obtained with the intersect function.

Below we compute the intersection of the two polygons from the previous example.

Pint = intersect(P1, P2)

Polyhedron DefaultPolyhedron{Float64, MixedMatHRep{Float64, Matrix{Float64}}, MixedMatVRep{Float64, Matrix{Float64}}}:
10-element iterator of HalfSpace{Float64, Vector{Float64}}:
 HalfSpace([0.8000000000000002, -1.0], 1.8200000000000003)
 HalfSpace([0.1076999257241891, -0.5025996533795494], 0.6497895518692746)
 HalfSpace([0.8620689655172415, 0.17241379310344826], 1.5862068965517244)
 HalfSpace([-0.0206611570247934, 0.36157024793388426], 0.21797520661157027)
 HalfSpace([-0.1050586220524305, 0.0047753919114740745], 0.19149321565011207)
 HalfSpace([0.6666666666666667, 1.0], 0.9666666666666668)
 HalfSpace([0.2977099236641222, 0.11450381679389314], 0.39847328244274816)
 HalfSpace([-0.11904761904761907, 1.0714285714285714], 0.9523809523809523)
 HalfSpace([-0.293965961835998, 0.26302217637957714], 0.44559051057246)
 HalfSpace([-0.004026150808106025, -0.17312448474855732], 0.20050231024367798)

While P1 and P2 have been constructed from their V-representation, their H-representation has been computed to build the intersection Pint.

hrepiscomputed(P1), vrepiscomputed(P1), hrepiscomputed(P2), vrepiscomputed(P2)

(true, true, true, true)

On the other hand, Pint is constructed from its H-representation hence its V-representation has not been computed yet.

hrepiscomputed(Pint), vrepiscomputed(Pint)

(true, false)

We can obtain the number of points in the intersection with npoints as follows:

npoints(Pint)

Note that this triggers the computation of the V-representation:

hrepiscomputed(Pint), vrepiscomputed(Pint)

(true, true)

We can plot the polygons and their intersection using the plot function.

using Plots
plot(P1, color="blue", alpha=0.2)
plot!(P2, color="red", alpha=0.2)
plot!(Pint, color="yellow", alpha=0.6)

This page was generated using Literate.jl.